package com.zlk.algorithm.dataStructure.graph.topological;

import com.zlk.algorithm.dataStructure.graph.impl.Graph;

import java.util.*;

/**
 * @program: algorithm
 * @ClassName Topological
 * @description: 依次遍历找到入读为0 要求 拓扑排序不能出现回环
 * @author: slfang
 * @create: 2024-03-19 16:27
 * @Version 1.0
 **/
public class TopologicalOrderBFS1 {

    public TopologicalOrderBFS1(Graph graph){

    }



    //OJ链接：https://www.lintcode.com/problem/topological-sorting
    public static class DirectedGraphNode {
        public int label;
        public ArrayList<DirectedGraphNode> neighbors;

        public DirectedGraphNode(int x) {
            label = x;
            neighbors = new ArrayList<DirectedGraphNode>();
        }
    }

    // 提交下面的
    public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
        HashMap<DirectedGraphNode,Integer>  inDegreeMap = new HashMap<>();
        for (DirectedGraphNode cur : graph) {
            inDegreeMap.put(cur,0);
        }

        for (int i = 0; i < graph.size(); i++) {
            DirectedGraphNode directedGraphNode = graph.get(i);
            for (DirectedGraphNode neighbor : directedGraphNode.neighbors) {
                inDegreeMap.put(neighbor,inDegreeMap.get(neighbor)+1);
            }
        }

//        for (DirectedGraphNode cur : graph) {
//            for (DirectedGraphNode next : cur.neighbors) {
//                inDegreeMap.put(next,inDegreeMap.get(next)+1);
//            }
//        }

        //todo
//        while (sortList.size()!=graph.size()){
//            for (Map.Entry<DirectedGraphNode, Integer> entry : inDegreeMap.entrySet()) {
//                if(entry.getValue()==0){
//                    DirectedGraphNode node = entry.getKey();
//                    for (DirectedGraphNode neighbor : node.neighbors) {
//                        inDegreeMap.put(neighbor,inDegreeMap.get(neighbor)-1);
//                    }
//                    sortList.add(node);
//                }
//            }
//        }

        Queue<DirectedGraphNode> zeroQueue = new LinkedList<>();
        for (DirectedGraphNode cur : inDegreeMap.keySet()) {
            if(inDegreeMap.get(cur)==0){
                zeroQueue.add(cur);
            }
        }
        ArrayList<DirectedGraphNode> ans = new ArrayList<>();
        while (!zeroQueue.isEmpty()){
            DirectedGraphNode cur = zeroQueue.poll();
            ans.add(cur);
            for (DirectedGraphNode next : cur.neighbors) {
                int newDegree = inDegreeMap.get(next) - 1;
                inDegreeMap.put(next,newDegree);
                if(newDegree==0){
                    zeroQueue.add(next);
                }
//                inDegreeMap.put(next, inDegreeMap.get(next) - 1);
//                if(inDegreeMap.get(next)==0){
//                    zeroQueue.offer(next);
//                }
            }
        }
        return ans;
    }






}
